555. The
nearest points
Anton began to
study mathematics at school. His attention was attracted to the new concept of
real line. Anton quickly learned how to calculate the distance between two
points on this line, to define segments and intervals on it.
Preparing for
the tests, Anton encountered the following problem: n points are given on the real line. Find two closest points among
them. The distance between two points x and y is defined as |x – y|.
Write a program
that helps Anton to solve the problem.
Input. The first line contains the number of points n (2 ≤ n ≤ 105). The second line contains n different
integers xi – coordinates
of the given points on the real line. The numbers in the row are separated by
one space. The value of each coordinate xi does not exceed 109
by absolute value.
Output. In the first
line you must print the minimum distance between two points, given in the
input. In the second line print the numbers of points, which corresponds to the
distance found. The points are numbered by integers from 1 to n in the order as they are coming in the
input. If there are multiple answers, print any of them.
|
Sample
input |
Sample
output |
|
5 10 3 6 2 5 |
1 2 4 |
SOLUTION
sort
Algorithm analysis
Sort the input coordinates
xi and find the minimum value
of their neighboring differences. We must memoize the number of the point
along with the abscissa. This can be done using a vector of pairs. The first element
of the pair is the abscissa of the point xi, the second element
is its number. The points are numbered from 1 to n.
Example
Consider the
state of the vector of pairs before and after sorting.
The smallest distance
between adjacent array elements after sorting is 1. It is reached, for example,
between points 4 and 2, or between points 5 and 3.
Algorithm realization
Declare a vector
of pairs v, where
each
element v[i] contains information about the i-th point (abscissa,
number).
vector<pair<int, int> > v;
Read the input
data. Create an array of points (points are numbered from 1 to n).
scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
{
scanf("%d",&x);
v[i] = make_pair(x,i+1);
}
Sort the points by the first element of the pair, that is, by the abscissa.
sort(v.begin(),v.end());
Find the smallest distance res between pairs of
adjacent points. In variables a and b store the numbers of these points.
res = 2e9;
for(i = 1; i < n; i++)
if
(v[i].first - v[i-1].first < res)
{
res = v[i].first - v[i-1].first;
a = v[i].second;
b = v[i-1].second;
}
Print the answer.
printf("%d\n%d %d\n",res,a,b);